/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-03-21
 * Time: 22:46
 */
public class QuickSort {
//
//
//    class Solution {
//        public int[] topKFrequent(int[] nums, int k) {
//
//            // 打印排序前的数组
//            System.out.println(Arrays.toString(nums));
//
//            // 执行快速排序操作
//            quickSort(nums,0,nums.length - 1);
//
//            // 打印排序后的数组
//            System.out.println(Arrays.toString(nums));
//
//            return null;
//        }
//
//
//        // 函数传入待排序数组 nums
//        // 排序区间的左端点 left
//        // 排序区间的右端点 right
//        private void quickSort(int[] nums,int left, int right){
//
//            // 如果 left 大于等于 right，说明该区间只有 1 个或者没有元素
//            if( left >=right ){
//                // 无需再递归划分后再排序，直接返回
//                return;
//            }
//
//            // 调用函数 partition，将 left 和 right 之间的元素划分为左右两部分
//            int mid = partition(nums,left,right);
//
//            // 划分之后，再对 mid 左侧的元素进行快速排序
//            quickSort(nums,left,mid - 1);
//
//            // 划分之后，再对 mid 右侧的元素进行快速排序
//            quickSort(nums,mid + 1,right);
//
//
//        }
//
//        private int partition(int[] nums, int left ,int right){
//
//            // 经典快速排序的写法
//            // 设置当前区间的第一个元素为基准元素
//            int pivot = nums[left];
//
//            // left 向右移动，right 向左移动，直到 left 和 right 指向同一元素为止
//            while( left < right ){
//
//                // 只有当遇到小于 pivot 的元素时，right 才停止移动
//                // 此时，right 指向了一个小于 pivot 的元素，这个元素不在它该在的位置上
//                while( left < right && nums[right] >= pivot ){
//                    // 如果 right 指向的元素是大于 pivot 的，那么
//                    // right 不断的向左移动
//                    right--;
//                }
//
//                // 将此时的 nums[left] 赋值为 nums[right]
//                // 执行完这个操作，比 pivot 小的这个元素被移动到了左侧
//                nums[left] = nums[right];
//
//
//                // 只有当遇到大于 pivot left 才停止移动
//                // 此时，left 指向了一个大于 pivot 的元素，这个元素不在它该在的位置上
//                while( left < right && nums[left] <= pivot){
//                    // 如果 left 指向的元素是小于 pivot 的，那么
//                    // left 不断的向右移动
//                    left++;
//                }
//
//                // 将此时的 nums[right] 赋值为 nums[left]
//                // 执行完这个操作，比 pivot 大的这个元素被移动到了右侧
//                nums[right] = nums[left];
//
//            }
//
//            // 此时，left 和 right 相遇，那么需要将此时的元素设置为 pivot
//            // 这个时候，pivot 的左侧元素都小于它，右侧元素都大于它
//            nums[left] = pivot;
//
//
//
//
//            // 返回 left
//            return left;
//
//        }
//    }
//class Solution {
//    public int[] topKFrequent(int[] nums, int k) {
//        //实现一个快速排序
//        System.out.println(Arrays.toString(nums));
//        QuickSort(nums,0,nums.length-1);
//        System.out.println(Arrays.toString(nums));
//        return null;
//    }
//
//
//    public void QuickSort(int[] nums,int left,int right) {
//        if(left>=right) {
//            return;
//        }
//        int mid =paration(nums,left,right);
//        //划分为三部分  [0,mid-1] mid [mid+1,right]
//        paration(nums,0,mid-1);
//        paration(nums,mid+1,right);
//    }
//    private int paration(int[] nums,int left,int right) {
//        //定义一个基准元素
//        int pivot =nums[left];//设置最左边元素为基准元素
//
//        //开始右边找小与左边交换左边找大与右边交换
//        while(left<right) {
//            //右边找小
//            while(left<right&&nums[right]>=pivot) {
//                right--;
//            }
//            //这是跳出while循环证明右边指针找到小那就把他移到左边（左指针的地方）
//            nums[left] =nums[right];
//            while(left<right&&nums[left]<=pivot) {
//                left++;
//            }
//            //这时跳出循环证明左边指针找到比pivot大的元素 将大的移动到右边
//            nums[right] =nums[left];
//        }
//        //此时跳出循环证明第一趟排序已经完成 我们将pivot的位置移动到left和right相遇的地方
//        nums[left] =pivot;
//        return left;
//    }


}

}
